import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        int[][] frame={{2,1,3},{6,5,4},{7,8,9}};
        int[] nums={1,0,2,3,0,4,5,0};
//        System.out.println(main.minFallingPathSum(frame));
        main.duplicateZeros(nums);
    }
    //珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        int m=frame.length;
        int n=frame[0].length;
        int[][] dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //下降路径最小和
    public int minFallingPathSum(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp=new int[m+1][n+2];
        for(int j=0;j<=n+1;j++){
            dp[0][j]=0;
        }
        for(int i=1;i<=m;i++){
            dp[i][0]=dp[i][n+1]=Integer.MAX_VALUE;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+matrix[i-1][j-1];
            }
        }
        int min=Integer.MAX_VALUE;
        for(int j=1;j<=n;j++){
            min=Math.min(min,dp[m][j]);
        }
        return min;
    }

    public void moveZeroes(int[] nums) {
        int dest=-1;
        for(int cur=0;cur<nums.length;cur++){
            if(nums[cur]!=0){
                swap(nums,cur,++dest);
            }
        }
    }

    private void swap(int[] nums, int cur, int i) {
        int temp=nums[cur];
        nums[cur]=nums[i];
        nums[i]=temp;
    }

    public void duplicateZeros(int[] arr) {
        //从后往前遍历，先找到复写的最后一个数组下标
        int cur=0;int dest=-1;
        for(;cur<arr.length;cur++){
            if(arr[cur]==0){
                dest+=2;
            }else{
                dest++;
            }
            if(dest>=arr.length-1){
                break;
            }
        }
        //第二步处理边界问题，因为这里dest可能越界
        if (dest == arr.length) {
            arr[arr.length-1]=0;
            dest-=2;
            cur--;
        }
        for(;cur>=0;cur--){
            if(arr[cur]==0){
                arr[dest--]=arr[dest--]=0;
            }else{
                arr[dest--]=arr[cur];
            }
        }
    }
}